package com.whitedust.top30;

import com.whitedust.structure.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author A
 * @since 2025/11/3 19:15
 */

public class Top26 {
    public static class MyObject {
        int value;

        MyObject(int value) {
            this.value = value;
        }
    }

    public static class MyComparator implements Comparator<MyObject> {
        @Override
        public int compare(MyObject o1, MyObject o2) {
            return Integer.compare(o1.value, o2.value); // 例如，按value值升序排列
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        //优先队列的比较写法
        //PriorityQueue<MyObject> pqs = new PriorityQueue<>(new MyComparator());
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
        for (ListNode list : lists) {
            while (list != null) {
                pq.offer(list);
                list = list.next;
            }
        }
        ListNode dummy = new ListNode(0, null);
        ListNode p = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            p.next = node;
            p = node;
            //一定要记得清空节点的next，否则最后一个加入节点的next不会null则会出现环
            p.next = null;
        }
        return dummy.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int left = 0;
        int right = lists.length - 1;
        return mergeList(lists, left, right);
    }

    private ListNode mergeList(ListNode[] lists, int left, int right) {
        //仅剩一个列表直接返回终止
        if (left == right) return lists[left];
        int mid = left + (right - left) / 2;
        //两边递归
        ListNode head1 = mergeList(lists, left, mid);
        ListNode head2 = mergeList(lists, mid + 1, right);
        return merge2List(head1, head2);
    }

    private ListNode merge2List(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0, null);
        ListNode tmp = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmp.next = head1;
                head1 = head1.next;
            } else {
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if (head1 == null) {
            tmp.next = head2;
        } else {
            tmp.next = head1;
        }
        return dummy.next;
    }
}
